package misa;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import pareto.ParetoSort;

public class MISA {
	
	//secondary population
	private List secondaryPopulation;
	private List secondaryPopulationVal;
	private List<Double> maxBound;
	private List<Double> minBound;
	private int[][] density;
	private int maxI = 0;
	private int maxJ = 0;
	private int maxDensity = 0;
	private double averageDensity = 0;
	private List crowedSolutionIndex;
	/**
	 * secondary population
	 */
	private List<List> population;
	private int dimension;
	private int popSize;
	private double leftBound;
	private double rightBound;
	private ObjectiveFunction objFunction;

	private int gridSize = 25;
	
	private int mutateN = 0;
	
	private Random rand;

	private List<List> valList;
	private List<Integer> indexList;
	private List<Integer> layerList;
	
	public MISA(int dimension, int popSize, int leftBound, int rightBound,
			ObjectiveFunction objFunction) {
		this.dimension = dimension;
		this.popSize = popSize;
		this.leftBound = leftBound;
		this.rightBound = rightBound;
		this.objFunction = objFunction;
		this.rand = new Random();
	}

	public void init() {
		InitialSolution init = new InitialSolution();
		population = init.randInit(dimension, popSize, leftBound,
				rightBound);
		this.secondaryPopulation = new ArrayList();
		this.secondaryPopulationVal = new ArrayList();
		
		getValList(population);

		
		/*List v = valList.get(indexList.get(0));
		for(int i=0;i<2;i++){
			System.out.println(v.get(0)+" "+v.get(1));
		}*/
		
		
		List selectedSolutions = new ArrayList();
		List selectedSolutionVals = new ArrayList();

		for (int i = 0; i < popSize * 0.05; i++) {
			int currentIndex = (Integer) indexList.get(i);

			updateSecondaryPopulation(population.get(currentIndex), valList.get(currentIndex));
			//secondaryPopulation.add(population.get(currentIndex));
			//secondaryPopulationVal.add(valList.get(currentIndex));

			selectedSolutions.add(population.get(currentIndex));
			selectedSolutionVals.add(valList.get(currentIndex));
		}

		
		List cloneSize = new ArrayList();
		
		if (secondaryPopulation.size() < popSize) {
			List distanceList = new ArrayList();
			double totalDistance = 0.0;

			for (int i = 0; i < selectedSolutions.size(); i++) {
				List currentVal = (ArrayList) selectedSolutionVals.get(i);
				double td = 0;
				for (int j = 0; j < population.size(); j++) {
					List tempVal = valList.get(j);
					td += ParetoSort.getDistance(currentVal, tempVal);
				}
				distanceList.add(td);
				totalDistance += td;
			}

			double averageDistance = totalDistance / distanceList.size();

			for (int i = 0; i < selectedSolutions.size(); i++) {
				double currentDistance = (Double) distanceList.get(i);

				if (currentDistance > averageDistance) {
					cloneSize.add(popSize * 12 / selectedSolutions.size());
				} else {
					cloneSize.add(popSize * 3 / selectedSolutions.size());
				}
			}

			

		} else {
			// if secondary population is full
			updateDensityOfSecondaryPop();	

			for (int i = 0; i < selectedSolutions.size(); i++) {
				List currentSolution = (ArrayList) selectedSolutions.get(i);
				boolean isCrowded = false;
				List<Double> currentSolutionVal = (ArrayList) selectedSolutionVals
						.get(i);
				double stepI = (maxBound.get(0) - minBound.get(0)) / gridSize;
				double stepJ = (maxBound.get(1) - minBound.get(1)) / gridSize;

				int currentI = (int) ((currentSolutionVal.get(0) - minBound
						.get(0))
						* gridSize / (maxBound.get(0) - minBound.get(0)));
				int currentJ = (int) ((currentSolutionVal.get(1) - minBound
						.get(1))
						* gridSize / (maxBound.get(1) - minBound.get(1)));

				if (currentI == maxI && currentJ == maxJ) {
					isCrowded = true;
				}
				if (isCrowded
						|| ParetoSort.checkIsContained(selectedSolutions,
								currentSolution)) {
					cloneSize.add(0);
				} else {
					if (density[currentI][currentJ] < averageDensity) {
						cloneSize.add(popSize * 12 / selectedSolutions.size());
					}else if (density[currentI][currentJ] > averageDensity){
						cloneSize.add(popSize * 3 / selectedSolutions.size());
					}else{
						cloneSize.add(popSize * 6 / selectedSolutions.size());
					}
				}
			}

		}

		
		//clone and mutation
		double mutateRateStep = (0.6-1/dimension)/(layerList.get(selectedSolutions.size()-1)-1);
		for(int i=0;i<selectedSolutions.size();i++){
			List currentSolution = (ArrayList)selectedSolutions.get(i);
			int size = (Integer)cloneSize.get(i);
			int currentMutatedN = mutateN + layerList.get(i);
			double mutateRate = 0.6-(layerList.get(i)-1)*mutateRateStep;
			for(int j=0;j<size;j++){
				List newSolution = new ArrayList();
				double r = Math.random();
				if(r<mutateRate){
					int mutatePosition = 0;
					if(dimension-currentMutatedN>0){
						mutatePosition = rand.nextInt(dimension-currentMutatedN);
					}
					for(int k=0;k<currentSolution.size();k++){
						if(k>=mutatePosition&&k<=mutatePosition+currentMutatedN){
							newSolution.add(rand.nextDouble()*(rightBound-leftBound)+leftBound);
						}else{
							newSolution.add(currentSolution.get(k));
						}
					}
					
				}else{
					for(int k=0;k<currentSolution.size();k++){
						newSolution.add(currentSolution.get(k));
					}
				}
				
				population.add(newSolution);
			}
		}
		
		getValList(population);
		List<List> newPopulation = new ArrayList();
		for(int i=0;i<popSize;i++){
			List s = population.get(i);
			newPopulation.add(s);
		}
		
		this.population = newPopulation;		
		
	}

	public List<List> getPopulation() {
		return population;
	}

	public void setPopulation(List<List> population) {
		this.population = population;
	}

	public List getSecondaryPopulation() {
		return secondaryPopulation;
	}

	public void setSecondaryPopulation(List secondaryPopulation) {
		this.secondaryPopulation = secondaryPopulation;
	}


	public List getSecondaryPopulationVal() {
		return secondaryPopulationVal;
	}

	public void setSecondaryPopulationVal(List secondaryPopulationVal) {
		this.secondaryPopulationVal = secondaryPopulationVal;
	}

	public int getDimension() {
		return dimension;
	}

	public void setDimension(int dimension) {
		this.dimension = dimension;
	}

	public int getPopSize() {
		return popSize;
	}

	public void setPopSize(int popSize) {
		this.popSize = popSize;
	}

	public double getLeftBound() {
		return leftBound;
	}

	public void setLeftBound(double leftBound) {
		this.leftBound = leftBound;
	}

	public double getRightBound() {
		return rightBound;
	}

	public void setRightBound(double rightBound) {
		this.rightBound = rightBound;
	}

	public ObjectiveFunction getObjFunction() {
		return objFunction;
	}

	public void setObjFunction(ObjectiveFunction objFunction) {
		this.objFunction = objFunction;
	}
	
	
	//calculate value for each solution
	private void getValList(List<List> pop){
		this.valList = new ArrayList();
		for(List solution:pop){
			List val = objFunction.getValue(solution);
			valList.add(val);
		}
		
		indexList = ParetoSort.sortPopulation(valList);
		layerList = new ArrayList();
		
		int currentLayer = 1;
		layerList.add(1);
		for(int i=1;i<indexList.size();i++){
			List previousSolution = pop.get(indexList.get(i-1));
			List followingSolution = pop.get(indexList.get(i));
			if(ParetoSort.compare(previousSolution, followingSolution)<0){
				currentLayer++;
				
			}
			layerList.add(currentLayer);
		}
	}
	
	//update secondary population
	private void updateSecondaryPopulation(List solution, List val){
		if(secondaryPopulation.size()<popSize){
			this.secondaryPopulation.add(solution);
			this.secondaryPopulationVal.add(val);
		}else{
			int removeIndex = rand.nextInt(crowedSolutionIndex.size());
			secondaryPopulation.remove(removeIndex);
			secondaryPopulationVal.remove(removeIndex);
			
			this.secondaryPopulation.add(solution);
			this.secondaryPopulationVal.add(val);
		}
		
	}

	//update density information of secondary population
	private void updateDensityOfSecondaryPop(){
		this.maxBound = new ArrayList();
		this.minBound = new ArrayList();

		List val = (ArrayList) secondaryPopulationVal.get(0);
		for (int i = 0; i < val.size(); i++) {
			maxBound.add((Double) val.get(i));
			minBound.add((Double) val.get(i));
		}

		for (int i = 1; i < secondaryPopulationVal.size(); i++) {
			val = (ArrayList) secondaryPopulationVal.get(i);
			for (int j = 0; j < val.size(); j++) {
				double currentVal = (Double) val.get(j);

				if (maxBound.get(j) < currentVal) {
					maxBound.set(j, currentVal);
				}

				if (minBound.get(j) > currentVal) {
					minBound.set(j, currentVal);
				}
			}
		}
		
		density = new int[gridSize][gridSize];
		for (int i = 0; i < secondaryPopulation.size(); i++) {
			val = (ArrayList) secondaryPopulationVal.get(i);
			List<Integer> xy = new ArrayList<Integer>();
			for (int j = 0; j < val.size(); j++) {
				double item = (Double) val.get(j);
				xy
						.add((int) ((item - minBound.get(j)) * gridSize / (maxBound
								.get(j) - minBound.get(j))));
			}

			density[xy.get(0)][xy.get(1)]++;
		}
		
		for (int i = 0; i < gridSize; i++) {
			for (int j = 0; j < gridSize; j++) {
				if (density[i][j] != 0) {
					averageDensity += density[i][j];
				}
				if (density[i][j] > maxDensity) {
					maxDensity = density[i][j];
					maxI = i;
					maxJ = j;
				}
			}
		}
		averageDensity = averageDensity / secondaryPopulation.size();
		
		crowedSolutionIndex = new ArrayList();
		double maxILeft = minBound.get(0)+(maxBound.get(0)-minBound.get(0))*maxI/gridSize;
		double maxIRight = minBound.get(0)+(maxBound.get(0)-minBound.get(0))*(maxI+1)/gridSize;
		double maxJLeft = minBound.get(1)+(maxBound.get(1)-minBound.get(1))*maxJ/gridSize;
		double maxJRight = minBound.get(1)+(maxBound.get(1)-minBound.get(1))*(maxJ+1)/gridSize;

		
		for(int i=0;i<secondaryPopulation.size();i++){
			List tempVal = (ArrayList)secondaryPopulationVal.get(i);
			double v1 = (Double)tempVal.get(0);
			double v2 = (Double)tempVal.get(1);
			if((v1>=maxILeft) &&( v1 < maxIRight) && (v2>= maxJLeft) && (v2 < maxJRight)){
				crowedSolutionIndex.add(i);
			}
		}
		
	}
	
	
	
	public List<Double> getMaxBound() {
		return maxBound;
	}

	public void setMaxBound(List<Double> maxBound) {
		this.maxBound = maxBound;
	}

	public List<Double> getMinBound() {
		return minBound;
	}

	public void setMinBound(List<Double> minBound) {
		this.minBound = minBound;
	}

	public int[][] getDensity() {
		return density;
	}

	public void setDensity(int[][] density) {
		this.density = density;
	}

	public int getMaxI() {
		return maxI;
	}

	public void setMaxI(int maxI) {
		this.maxI = maxI;
	}

	public int getMaxJ() {
		return maxJ;
	}

	public void setMaxJ(int maxJ) {
		this.maxJ = maxJ;
	}

	public int getMaxDensity() {
		return maxDensity;
	}

	public void setMaxDensity(int maxDensity) {
		this.maxDensity = maxDensity;
	}

	public double getAverageDensity() {
		return averageDensity;
	}

	public void setAverageDensity(double averageDensity) {
		this.averageDensity = averageDensity;
	}

	public List getCrowedSolutionIndex() {
		return crowedSolutionIndex;
	}

	public void setCrowedSolutionIndex(List crowedSolutionIndex) {
		this.crowedSolutionIndex = crowedSolutionIndex;
	}

	public int getGridSize() {
		return gridSize;
	}

	public void setGridSize(int gridSize) {
		this.gridSize = gridSize;
	}

	public int getMutateN() {
		return mutateN;
	}

	public void setMutateN(int mutateN) {
		this.mutateN = mutateN;
	}

	public Random getRand() {
		return rand;
	}

	public void setRand(Random rand) {
		this.rand = rand;
	}

	public List<List> getValList() {
		return valList;
	}

	public void setValList(List<List> valList) {
		this.valList = valList;
	}

	public List<Integer> getIndexList() {
		return indexList;
	}

	public void setIndexList(List<Integer> indexList) {
		this.indexList = indexList;
	}

	public List<Integer> getLayerList() {
		return layerList;
	}

	public void setLayerList(List<Integer> layerList) {
		this.layerList = layerList;
	}

	public static void main(String[] args) {
		ObjectiveFunction objFun = new ObjectiveFunction();
		MISA misa = new MISA(2, 100, 0, 1, objFun);
		for(int i=0;i<1000;i++){
			misa.init();
		}
		
		List pop = misa.getPopulation();
		misa.getValList(pop);
		
		List l = misa.getLayerList();
		for(Object o:l){
			System.out.println(o);
		}
	}
	
}
